package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/11/23.<br><br>
 *
 * 中等：字符串相乘
 */
public class Topic43 {

    public static void main(String[] args) {
        Topic43 instance = new Topic43();

        System.out.println(instance.multiply("2", "3"));
        System.out.println(instance.multiply("9", "99"));
        System.out.println(instance.multiply("123", "456"));
        System.out.println(instance.multiply("123456789", "987654321"));
    }

    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        int len1 = num1.length();
        int len2 = num2.length();
        char[] array1 = num1.toCharArray();
        char[] array2 = num2.toCharArray();
        int[] intArray = new int[len1 + len2];

        for(int i = len1 - 1; i >= 0; i--) {
            for(int j = len2 - 1; j >= 0; j--) {
                intArray[i + j + 1] += (array1[i] - '0') * (array2[j] - '0');
            }
        }

        for(int i = len1 + len2 - 1; i > 0; i--) {
            intArray[i - 1] += intArray[i] / 10;
            intArray[i] %= 10;
        }

        int index = intArray[0] == 0 ? 1 : 0;
        StringBuilder builder = new StringBuilder();
        while (index < len1 + len2) {
            builder.append(intArray[index++]);
        }

        return builder.toString();
    }

    public String multiply2(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        int len1 = num1.length();
        int len2 = num2.length();
        char[] array1 = num1.toCharArray();
        char[] array2 = num2.toCharArray();

        String result = "0";
        for(int i = len2 - 1; i >= 0; i--) {
            StringBuilder builder = new StringBuilder();

            for(int k = i; k < len2 - 1; k++) {
                builder.append("0");
            }

            int carry = 0;
            for(int j = len1 - 1; j >= 0; j--) {
                int value = (array1[j] - '0') * (array2[i] - '0') + carry;
                builder.append(value % 10);
                carry = value / 10;
            }

            if(carry != 0) {
                builder.append(carry);
            }

            result = addStrings(result, builder.reverse().toString());
        }

        return result;
    }

    private String addStrings(String num1, String num2) {
        int start1 = num1.length() - 1;
        int start2 = num2.length() - 1;

        int carry = 0;
        char[] array1 = num1.toCharArray();
        char[] array2 = num2.toCharArray();
        StringBuilder builder = new StringBuilder();
        while (start1 >= 0 || start2 >= 0) {
            int digit1 = start1 >= 0 ? array1[start1] - '0' : 0;
            int digit2 = start2 >= 0 ? array2[start2] - '0' : 0;
            int temp = digit1 + digit2 + carry;
            if(temp > 9) {
                temp = temp - 10;
                carry = 1;
            }
            else {
                carry = 0;
            }

            builder.append(temp);
            start1--;
            start2--;
        }

        if(carry == 1) {
            builder.append(carry);
        }

        return builder.reverse().toString();
    }
}
